OK, so welcome for our computer graphics lecture.

So today I want to finish a nice algorithm

for traversing KD trees.

It's a way to intersect rays with a scene,

with a set of triangles.

It's based on a data structure of a KD tree

that we can see here.

So the idea is that we have a bounding box

for the entire scene that is hierarchically subdivided.

And it's always subdivided into two halves.

It's subdivided by a split plane that

is parallel to the three coordinate axes.

OK, it's perpendicular to the three coordinate axes.

So we can split the bounding box along x, y, or z.

And we always split it at an arbitrary position

of that plane so that plane can be moved forward and backward.

It's not always directly in the middle.

So that's the basis.

And now we assume that we have a ray.

And we know it intersects the bounding box

of the entire scene.

I mean, otherwise, the ray cannot hit anything.

So then it's trivial.

Now we assume we have such a ray.

We know it intersects our bounding box.

And we also compute the ray parameter

of where the ray enters the current bounding box

and where it leaves it.

So that's t min, t max.

OK, so that's the kind of state that we have.

So we know we have this box.

We have this entrance parameter and this exit parameter.

And good.

So that's essentially the same situation

that I've drawn here on the blackboard.

So our box, this is the ray.

This is the entrance point.

And this is the exit point.

OK, now we have two possibilities.

So one case is that this box here

is the leaf of our hierarchy.

That means there are no further sub boxes.

And that means that this box here contains a set of triangles

that are intersecting this box.

So in that case, we just intersect that ray

with the remaining triangles.

The test for this, we were speaking about last week,

how to intersect, or on Tuesday, how

to intersect a triangle with a single ray.

This we know how to do.